package _18_剑指OfferII;

import java.util.*;

public class _108_剑指OfferII单词演变 {

    public static void main(String[] args) {

        _108_剑指OfferII单词演变 v = new _108_剑指OfferII单词演变();
        String str1 = "hit";
        String str2 = "cog";
        List<String> list = new ArrayList<>();
        list.add("hot");
        list.add("dot");
        list.add("dog");
        list.add("lot");
        list.add("log");
        list.add("cog");
        System.out.println(v.ladderLength(str1, str2, list));

    }

    // 双向BFS查找
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) {
            return 0;
        }
        Set<String> beginVis = new HashSet<>(), endVis = new HashSet<>();
        beginVis.add(beginWord);
        endVis.add(endWord);
        Queue<String> begin = new LinkedList<>(), end = new LinkedList<>();
        begin.add(beginWord);
        end.add(endWord);
        int step = 0;
        while (!begin.isEmpty() && !end.isEmpty()) {
            if (begin.size() > end.size()) {
                Set<String> tv = beginVis;
                beginVis = endVis;
                endVis = tv;
                Queue<String> tq = begin;
                begin = end;
                end = tq;
            }
            step++;
            int size = begin.size();
            while (size-- > 0) {
                String cur = begin.poll();
                char[] curChar = cur.toCharArray();
                for (int i = 0; i < curChar.length; ++i) {
                    char ch = curChar[i];
                    for (char c = 'a'; c <= 'z'; ++c) {
                        curChar[i] = c;
                        String s = String.valueOf(curChar);
                        if (endVis.contains(s)) return step + 1;
                        if (wordSet.contains(s) && !beginVis.contains(s)) {
                            begin.offer(s);
                            beginVis.add(s);
                        }
                    }
                    curChar[i] = ch;
                }
            }
        }
        return 0;
    }


    public boolean isSingleDiff(String str1, String str2) {
        if (str1.equals(str2)) return false;
        boolean isDiff = false;
        for (int i = 0; i < str1.length(); ++i) {
            if (str1.charAt(i) != str2.charAt(i)) {
                if (isDiff) return false;
                isDiff = true;
            }
        }
        return true;
    }

    // 广度搜索，千万记得，广度搜索，加入队列元素一定要设置标记，这样就可以避免出现重复计算问题
    public int ladderLength1(String beginWord, String endWord, List<String> wordList) {
        if (!wordList.contains(endWord)) return 0;
        Set<String> containers = new HashSet<>(wordList);
        Queue<String> queue = new LinkedList<>();
        Iterator<String> iterator = containers.iterator();
        while (iterator.hasNext()) {
            String value = iterator.next();
            if (isSingleDiff(beginWord, value)) {
                queue.add(value);
                iterator.remove();
            }
        }
        int level = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            level++;
            while (size-- > 0) {
                String poll = queue.poll();
                if (poll.equals(endWord)) return level;
                Iterator<String> temp = containers.iterator();
                while (temp.hasNext()) {
                    String value = temp.next();
                    if (isSingleDiff(poll, value)) {
                        queue.add(value);
                        temp.remove();
                    }
                }
            }
        }
        return 0;
    }

}
